home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / msdos / raytrace / pov / bin / xtras / addon1.c < prev    next >
C/C++ Source or Header  |  1994-09-11  |  55KB  |  2,440 lines
  1. /****************************************************************************
  2. *
  3. *  ATTENTION!!!
  4. *
  5. *  THIS FILE HAS BEEN MODIFIED!!! IT IS NOT PART OF THE OFFICAL
  6. *  POV-RAY 2.2 DISTRIBUTION!!!
  7. *
  8. *  THIS FILE IS PART OF "FASTER THAN POV-RAY" (VERSION 2.2),
  9. *  A SPED-UP VERSION OF POV-RAY 2.2. USE AT YOUR OWN RISK!!!!!!
  10. *
  11. *  New files: addon0.c, addon1.c, addon2.c, addon3.c, addon.h
  12. *
  13. *  The additional modules were written by Dieter Bayer.
  14. *
  15. *  Send comments, suggestions, bugs, ideas ... to:
  16. *
  17. *  e-mail: dieter@cip.e-technik.uni-erlangen.de
  18. *  CIS: 100255.3074
  19. *
  20. *  All changed/added lines are enclosed in #ifdef DB_CODE ... #endif
  21. *
  22. *  The vista projection was taken from:
  23. *
  24. *    A. Hashimoto, T. Akimoto, K. Mase, and Y. Suenaga, 
  25. *    "Vista Ray-Tracing: High Speed Ray Tracing Using Perspective
  26. *    Projection Image", New Advances in Computer Graphics, Proceedings
  27. *    of CG International '89, R. A. Earnshaw, B. Wyvill (Eds.), 
  28. *    Springer, ..., pp. 549-560
  29. *
  30. *  The idea for the light buffer was taken from:
  31. *
  32. *    E. Haines and D. Greenberg, "The Light Buffer: A Shadow-Testing 
  33. *    Accelerator", IEEE CG&A, Vol. 6, No. 9, Sept. 1986, pp. 6-16
  34. *
  35. *****************************************************************************/
  36.  
  37. /****************************************************************************
  38. *  addon1.c
  39. *
  40. *  This module was written by Dieter Bayer.
  41. *
  42. *  This module contains functions used only for the vista buffer.
  43. *
  44. *  01.03.1994 : Creation
  45. *
  46. *  29.04.1994 : Version 2.0
  47. *
  48. ******************************************************************************/
  49.  
  50. #include <time.h>
  51. #include "frame.h"
  52. #include "vector.h"
  53. #include "povproto.h"
  54. #include "addon.h"
  55.  
  56. #ifdef DB_CODE
  57.  
  58. /* count project tests */
  59. #define COUNT_PROJECT_TESTS
  60.  
  61. #define NUMBER_OF_TYPES      18
  62. #define TYPE_BICUBIC_PATCH    0
  63. #define TYPE_BLOB             1
  64. #define TYPE_BOX              2
  65. #define TYPE_CONE             3
  66. #define TYPE_CSG_INTERSECTION 4
  67. #define TYPE_CSG_MERGE        5
  68. #define TYPE_CSG_UNION        6
  69. #define TYPE_DISC             7
  70. #define TYPE_ELLIPSOID        8
  71. #define TYPE_HEIGHT_FIELD     9
  72. #define TYPE_LIGHT_SOURCE    10
  73. #define TYPE_PLANE           11
  74. #define TYPE_POLY            12
  75. #define TYPE_QUADRIC         13
  76. #define TYPE_SMOOTH_TRIANGLE 14
  77. #define TYPE_SPHERE          15
  78. #define TYPE_TRIANGLE        16
  79. #define TYPE_UNKNOWN         17
  80.  
  81. #define NUMBER_OF_FLAGS     9
  82. #define FLAG_SUM            0
  83. #define FLAG_INFINITE       1
  84. #define FLAG_SCREEN_FILLING 2
  85. #define FLAG_USED_IN_CSG    3
  86. #define FLAG_INVISIBLE      4
  87. #define FLAG_BOUNDED        5
  88. #define FLAG_CLIPPED        6
  89. #define FLAG_BOUND_OBJECT   7
  90. #define FLAG_CLIP_OBJECT    8
  91.  
  92.  
  93.  
  94. /*****************************************************************************
  95. * external variables
  96. ******************************************************************************/
  97.  
  98. extern long Number_Of_Rays;
  99. extern FRAME Frame;
  100. extern int Trace_Level;
  101. extern int Use_Slabs;
  102. extern DBL Max_Trace_Level;
  103. extern time_t tstart, tstop;
  104. extern unsigned int Options;
  105. extern OBJECT *Root_Object;
  106.  
  107. extern METHODS Bicubic_Patch_Methods;
  108. extern METHODS Blob_Methods;
  109. extern METHODS Box_Methods;
  110. extern METHODS Cone_Methods;
  111. extern METHODS Csg_Height_Field_Methods;
  112. extern METHODS CSG_Intersection_Methods;
  113. extern METHODS CSG_Merge_Methods;
  114. extern METHODS CSG_Union_Methods;
  115. extern METHODS Disc_Methods;
  116. extern METHODS Ellipsoid_Methods;
  117. extern METHODS Height_Field_Methods;
  118. extern METHODS Light_Source_Methods;
  119. extern METHODS Plane_Methods;
  120. extern METHODS Poly_Methods;
  121. extern METHODS Quadric_Methods;
  122. extern METHODS Smooth_Triangle_Methods;
  123. extern METHODS Sphere_Methods;
  124. extern METHODS Triangle_Methods;
  125.  
  126. extern unsigned MAXQUEUE;
  127. extern unsigned long totalQueues, totalQueueResets, nChecked, nEnqueued;
  128.  
  129. extern size_t Mem_Vista_Buffer;
  130.  
  131.  
  132.  
  133. /*****************************************************************************
  134. * Non-static variables
  135. ******************************************************************************/
  136.  
  137. PROJECT_TREE_NODE *Root_Vista;
  138. unsigned long Project_Tests = 0, Project_Tests_Succeeded = 0;
  139. unsigned Project_Algorithm = PROJECTIONS_WITH_LEAF_SLABS;
  140.  
  141.  
  142.  
  143.  
  144. /*****************************************************************************
  145. * Static variables
  146. ******************************************************************************/
  147.  
  148. static DBL distance;
  149. static MATRIX WC2VC, WC2VCinv;
  150. static VECTOR O, U, V, W;
  151.  
  152. /* Planes for 3d-clipping */
  153.  
  154. static VECTOR VIEW_VX1 = {-0.8944271910, 0.0, -0.4472135955};
  155. static VECTOR VIEW_VX2 = { 0.8944271910, 0.0, -0.4472135955};
  156. static VECTOR VIEW_VY1 = {0.0, -0.8944271910, -0.4472135955};
  157. static VECTOR VIEW_VY2 = {0.0,  0.8944271910, -0.4472135955};
  158. static DBL VIEW_DX1 = 0.4472135955;
  159. static DBL VIEW_DX2 = 0.4472135955;
  160. static DBL VIEW_DY1 = 0.4472135955;
  161. static DBL VIEW_DY2 = 0.4472135955;
  162.  
  163. /* Queues */
  164.  
  165. static Qelem *Tree_Leaf_Queue;
  166. static PROJECT_TREE_NODE **Tree_Node_Queue;
  167.  
  168.  
  169.  
  170. /*****************************************************************************
  171. * Static functions
  172. ******************************************************************************/
  173.  
  174. static void Project_rectangle PARAMS((PROJECT *Project, VECTOR P1, VECTOR P2, VECTOR P3, VECTOR P4, int *visible));
  175. static void Project_triangle PARAMS((PROJECT *Project, VECTOR P1, VECTOR P2, VECTOR P3, int *visible));
  176.  
  177. static void Project_Bbox PARAMS((PROJECT *Project, VECTOR *Points, int *visible));
  178. static void Project_Bounds PARAMS((PROJECT *Project, BBOX *Bounds, int *visible));
  179.  
  180. static void Get_Perspective_Projection PARAMS((OBJECT *Object, PROJECT *Project, int infinite));
  181.  
  182. static void Project_Object PARAMS((OBJECT *Object, PROJECT *Project));
  183.  
  184. static void Project_Bicubic_Patch PARAMS((PROJECT *Project, OBJECT *Object));
  185. static void Project_Box PARAMS((PROJECT *Project, OBJECT *Object, int *visible));
  186. static void Project_Height_Field PARAMS((PROJECT *Project, OBJECT *Object, int *visible));
  187. static void Project_Sphere PARAMS((PROJECT *Project, OBJECT *Object));
  188. static void Project_Triangle PARAMS((PROJECT *Project, OBJECT *Object, int *visible));
  189. static void Project_Smooth_Triangle PARAMS((PROJECT *Project, OBJECT *Object, int *visible));
  190.  
  191. static void Get_Ellipse_Projection PARAMS((PROJECT *Project, DBL a20, DBL a02, DBL a11, DBL a10, DBL a01, DBL a00));
  192.  
  193. static void Transform_Point PARAMS((VECTOR *P));
  194.  
  195. static void Project_Bounding_Slab PARAMS((PROJECT *Project, PROJECT_TREE_NODE **Tree, OBJECT *Object));
  196.  
  197. static void Create_Rayinfo PARAMS((RAY *Ray, RAYINFO *rayinfo));
  198.  
  199. static int Intersect_Vista_Tree PARAMS((RAY *Ray, PROJECT_TREE_NODE *Tree, int x, INTERSECTION *Best_Intersection));
  200.  
  201.  
  202.  
  203.  
  204. /*****************************************************************************
  205. *
  206. * FUNCTION      : Init_Project_Tree_Queues
  207. *
  208. * ARGUMENTS     : none
  209. *
  210. * MODIFIED ARGS : none
  211. *
  212. * RETURN VALUE  : none
  213. *
  214. * AUTHOR        : Dieter Bayer, May 1994
  215. *
  216. * DESCRIPTION
  217. *
  218. *   Init queues for descending project tress, i.e. allocate memory needed.
  219. *
  220. * CHANGES
  221. *
  222. *   -
  223. *
  224. ******************************************************************************/
  225.  
  226. void Init_Project_Tree_Queues()
  227. {
  228.   Tree_Leaf_Queue = (Qelem *)VB_malloc(MAXQUEUE*sizeof(Qelem));
  229.  
  230.   if (Tree_Leaf_Queue == NULL)
  231.   {
  232.     Fatal_MAError("priority queue for vista/light buffer");
  233.   }
  234.  
  235.   Tree_Node_Queue = (PROJECT_TREE_NODE **)VB_malloc(MAXQUEUE*sizeof(PROJECT_TREE_NODE *));
  236.  
  237.   if (Tree_Node_Queue == NULL)
  238.   {
  239.     Fatal_MAError("priority queue for vista/light buffer");
  240.   }
  241. }
  242.  
  243.  
  244.  
  245. /*****************************************************************************
  246. *
  247. * FUNCTION      : Prune_Vista_Tree
  248. *
  249. * ARGUMENTS     : y - Current scanline number
  250. *
  251. * MODIFIED ARGS : none
  252. *
  253. * RETURN VALUE  : none
  254. *
  255. * AUTHOR        : Dieter Bayer, May 1994
  256. *
  257. * DESCRIPTION
  258. *
  259. *   Prune vista tree, i.e. mark all nodes not on the current line inactive.
  260. *
  261. * CHANGES
  262. *
  263. *   -
  264. *
  265. ******************************************************************************/
  266.  
  267. void Prune_Vista_Tree(y)
  268. int y;
  269. {
  270.   unsigned size;
  271.   unsigned short i;
  272.   PROJECT_TREE_NODE *Node, *Sib;
  273.  
  274.   size = 0;
  275.  
  276. #ifdef COUNT_PROJECT_TESTS
  277.   Project_Tests++;
  278. #endif
  279.  
  280.   if ((y < Root_Vista->Project.y1) || (y > Root_Vista->Project.y2))
  281.   {
  282.     /* Root doesn't lie on current line --> prune root */
  283.  
  284.     Root_Vista->is_leaf |= PRUNE_TEMPORARY;
  285.   }
  286.   else
  287.   {
  288.     /* Root lies on current line --> unprune root */
  289.  
  290. #ifdef COUNT_PROJECT_TESTS
  291.     Project_Tests_Succeeded++;
  292. #endif
  293.  
  294.     Root_Vista->is_leaf &= PRUNE_TEMPORARY_INVERS;
  295.  
  296.     Tree_Node_Queue[size++] = Root_Vista;
  297.   }
  298.  
  299.   while (size > 0)
  300.   {
  301.     Node = Tree_Node_Queue[--size];
  302.  
  303.     if (Node->is_leaf & TRUE)
  304.     {
  305. #ifdef COUNT_PROJECT_TESTS
  306.       Project_Tests++;
  307. #endif
  308.  
  309.       if ((y < Node->Project.y1) || (y > Node->Project.y2))
  310.       {
  311.     /* Leaf doesn't lie on current line --> prune leaf */
  312.  
  313.     Node->is_leaf |= PRUNE_TEMPORARY;
  314.       }
  315.       else
  316.       {
  317.     /* Leaf lies on current line --> unprune leaf */
  318.  
  319. #ifdef COUNT_PROJECT_TESTS
  320.     Project_Tests_Succeeded++;
  321. #endif
  322.  
  323.     Node->is_leaf &= PRUNE_TEMPORARY_INVERS;
  324.       }
  325.     }
  326.     else
  327.     {
  328.       /* Check siblings of the node */
  329.  
  330.       for (i = 0; i < Node->Entries; i++)
  331.       {
  332.     Sib = Node->Entry[i];
  333.  
  334. #ifdef COUNT_PROJECT_TESTS
  335.     Project_Tests++;
  336. #endif
  337.  
  338.     if ((y < Sib->Project.y1) || (y > Sib->Project.y2))
  339.     {
  340.       /* Sibling doesn't lie on current line --> prune sibling */
  341.  
  342.       Sib->is_leaf |= PRUNE_TEMPORARY;
  343.     }
  344.     else
  345.     {
  346.       /* Sibling lies on current line --> unprune sibling */
  347.  
  348. #ifdef COUNT_PROJECT_TESTS
  349.       Project_Tests_Succeeded++;
  350. #endif
  351.  
  352.       Sib->is_leaf &= PRUNE_TEMPORARY_INVERS;
  353.  
  354.       /* Add sibling to list */
  355.  
  356.       Tree_Node_Queue[size++] = Sib;
  357.     }
  358.       }
  359.     }
  360.   }
  361. }
  362.  
  363.  
  364.  
  365. /*****************************************************************************
  366. *
  367. * FUNCTION      : Trace_Primary_Ray
  368. *
  369. * ARGUMENTS     : Ray    - Current ray
  370. *                 Colour - Ray's colour
  371. *                 x      - Current x-coordinate
  372. *
  373. * MODIFIED ARGS : colour
  374. *
  375. * RETURN VALUE  : none
  376. *
  377. * AUTHOR        : Dieter Bayer, May 1994
  378. *
  379. * DESCRIPTION
  380. *
  381. *   Trace a primary ray using the vista tree.
  382. *
  383. * CHANGES
  384. *
  385. *   -
  386. *
  387. ******************************************************************************/
  388.  
  389. void Trace_Primary_Ray (Ray, Colour, x)
  390. RAY *Ray;
  391. COLOUR *Colour;
  392. int x;
  393. {
  394.   INTERSECTION Best_Intersection;
  395.  
  396.   COOPERATE
  397.  
  398.   Number_Of_Rays++;
  399.  
  400.   if (Trace_Level > (int)Max_Trace_Level)
  401.     return;
  402.  
  403.   Colour->Red = Colour->Green = Colour->Blue = 0.0;
  404.  
  405.   Best_Intersection.Depth = BOUND_HUGE;
  406.  
  407.   /* What objects does this ray intersect? */
  408.  
  409.   if (Intersect_Vista_Tree(Ray, Root_Vista, x, &Best_Intersection))
  410.   {
  411.     Determine_Apparent_Colour (&Best_Intersection, Colour, Ray);
  412.   }
  413.   else
  414.   {
  415.     if (Frame.Fog_Distance > 0.0)
  416.     {
  417.       *Colour = Frame.Fog_Colour;
  418.     }
  419.     else
  420.     {
  421.       *Colour = Frame.Background_Colour;
  422.     }
  423.   }
  424. }
  425.  
  426.  
  427.  
  428. /*****************************************************************************
  429. *
  430. * FUNCTION      : Create_Rayinfo
  431. *
  432. * ARGUMENTS     : Ray     - Current ray
  433. *                 rayinfo - Rayinfo structure
  434. *
  435. * MODIFIED ARGS : rayinfo
  436. *
  437. * RETURN VALUE  : none
  438. *
  439. * AUTHOR        : Dieter Bayer, May 1994
  440. *
  441. * DESCRIPTION
  442. *
  443. *   Calculate the rayinfo structure for a given ray. It's need for
  444. *   intersection the ray with bounding boxes.
  445. *
  446. * CHANGES
  447. *
  448. *   -
  449. *
  450. ******************************************************************************/
  451.  
  452. static void Create_Rayinfo(Ray, rayinfo)
  453. RAY *Ray;
  454. RAYINFO *rayinfo;
  455. {
  456.   DBL t;
  457.  
  458.   /* Create the direction vectors for this ray */
  459.  
  460.   rayinfo->slab_num = Ray->Initial;
  461.  
  462.   if ((rayinfo->nonzero.x = ((t = Ray->Direction.x) != 0.0)) != 0)
  463.   {
  464.     rayinfo->slab_den.x = 1.0 / t;
  465.     rayinfo->positive.x = (Ray->Direction.x > 0.0);
  466.   }
  467.  
  468.   if ((rayinfo->nonzero.y = ((t = Ray->Direction.y) != 0.0)) != 0)
  469.   {
  470.     rayinfo->slab_den.y = 1.0 / t;
  471.     rayinfo->positive.y = (Ray->Direction.y > 0.0);
  472.   }
  473.  
  474.   if ((rayinfo->nonzero.z = ((t = Ray->Direction.z) != 0.0)) != 0)
  475.   {
  476.     rayinfo->slab_den.z = 1.0 / t;
  477.     rayinfo->positive.z = (Ray->Direction.z > 0.0);
  478.   }
  479. }
  480.  
  481.  
  482.  
  483. /*****************************************************************************
  484. *
  485. * FUNCTION      : Intersect_Vista_Tree
  486. *
  487. * ARGUMENTS     : Ray               - Primary ray
  488. *                 Tree              - Vista tree's top-node
  489. *                 x                 - Current x-coordinate
  490. *                 Best_Intersection - Intersection found
  491. *
  492. * MODIFIED ARGS : Best_Intersection
  493. *
  494. * RETURN VALUE  : none
  495. *
  496. * AUTHOR        : Dieter Bayer, May 1994
  497. *
  498. * DESCRIPTION
  499. *
  500. *   Intersect a PRIMARY ray with the vista tree
  501. *   (tree pruning is used can be primary ray!!!).
  502. *
  503. * CHANGES
  504. *
  505. *   -
  506. *
  507. ******************************************************************************/
  508.  
  509. static int Intersect_Vista_Tree(Ray, Tree, x, Best_Intersection)
  510. RAY *Ray;
  511. PROJECT_TREE_NODE *Tree;
  512. int x;
  513. INTERSECTION *Best_Intersection;
  514. {
  515.   INTERSECTION New_Intersection;
  516.   unsigned short i;
  517.   unsigned Qsize, size;
  518.   int Found;
  519.   RAYINFO rayinfo;
  520.   DBL key;
  521.   OBJECT *Object;
  522.   PROJECT_TREE_NODE *Node;
  523.  
  524.   /* Start with an empty priority queue */
  525.  
  526.   Qsize = 0;
  527.  
  528.   Found = FALSE;
  529.  
  530.   totalQueueResets++;
  531.  
  532.   /* Which algorithm to use? */
  533.  
  534.   switch (Project_Algorithm)
  535.   {
  536.     /************************************************************************
  537.     * Do not use any bounding slab tests. just use their projections.
  538.     *************************************************************************/
  539.  
  540.     case PROJECTIONS_WITHOUT_SLABS :
  541.  
  542.       /* Check root */
  543.  
  544. #ifdef COUNT_PROJECT_TESTS
  545.       Project_Tests++;
  546. #endif
  547.  
  548.       if ((x >= Tree->Project.x1) && (x <= Tree->Project.x2))
  549.       {
  550. #ifdef COUNT_PROJECT_TESTS
  551.     Project_Tests_Succeeded++;
  552. #endif
  553.  
  554.     Tree_Node_Queue[Qsize++] = Tree;
  555.       }
  556.  
  557.       while (Qsize > 0)
  558.       {
  559.     Tree = Tree_Node_Queue[--Qsize];
  560.  
  561.     switch (Tree->is_leaf)
  562.     {
  563.       case FALSE:
  564.  
  565.         /* Check siblings of the unpruned node in 2d */
  566.  
  567.         for (i = 0; i < Tree->Entries; i++)
  568.         {
  569.           Node = Tree->Entry[i];
  570.  
  571.           /* Check unpruned siblings only */
  572.  
  573.           if (Node->is_leaf < PRUNE_CHECK)
  574.           {
  575. #ifdef COUNT_PROJECT_TESTS
  576.         Project_Tests++;
  577. #endif
  578.  
  579.         if ((x >= Node->Project.x1) && (x <= Node->Project.x2))
  580.         {
  581. #ifdef COUNT_PROJECT_TESTS
  582.           Project_Tests_Succeeded++;
  583. #endif
  584.  
  585.           /* Add node to node queue */
  586.  
  587.           if (Qsize >= MAXQUEUE)
  588.             Fatal_Error("Node queue overflow.\n");
  589.  
  590.           Tree_Node_Queue[Qsize++] = Node;
  591.         }
  592.           }
  593.         }
  594.  
  595.         break;
  596.  
  597.       case TRUE:
  598.  
  599.         /* Unpruned leaf --> test object */
  600.  
  601.         if (Intersection(&New_Intersection, ((PROJECT_TREE_LEAF *)Tree)->Object, Ray))
  602.         {
  603.           if (New_Intersection.Depth < Best_Intersection->Depth)
  604.           {
  605.         *Best_Intersection = New_Intersection;
  606.         Found = TRUE;
  607.           }
  608.         }
  609.  
  610.         break;
  611.  
  612.        /* default:
  613.  
  614.         The node/leaf is pruned and needn't be checked */
  615.  
  616.     }
  617.       }
  618.  
  619.       break;
  620.  
  621.  
  622.  
  623.     /************************************************************************
  624.     * Use bounding slab tests for leaves (i.e. objects) in the tree.
  625.     *************************************************************************/
  626.  
  627.     case PROJECTIONS_WITH_LEAF_SLABS :
  628.  
  629.       /* Create the direction vectors for this ray */
  630.  
  631.       Create_Rayinfo(Ray, &rayinfo);
  632.  
  633.       /* Fill the priority queue with all possible candidates */
  634.  
  635.       size = 0;
  636.  
  637.       /* Check root */
  638.  
  639. #ifdef COUNT_PROJECT_TESTS
  640.       Project_Tests++;
  641. #endif
  642.  
  643.       if ((x >= Tree->Project.x1) && (x <= Tree->Project.x2))
  644.       {
  645. #ifdef COUNT_PROJECT_TESTS
  646.     Project_Tests_Succeeded++;
  647. #endif
  648.  
  649.     Tree_Node_Queue[size++] = Tree;
  650.       }
  651.  
  652.       while (size > 0)
  653.       {
  654.     Tree = Tree_Node_Queue[--size];
  655.  
  656.     switch (Tree->is_leaf)
  657.     {
  658.       case FALSE:
  659.  
  660.         /* Check siblings of the unpruned node in 2d */
  661.  
  662.         for (i = 0; i < Tree->Entries; i++)
  663.         {
  664.           Node = Tree->Entry[i];
  665.  
  666.           /* Check unpruned siblings only */
  667.  
  668.           if (Node->is_leaf < PRUNE_CHECK)
  669.           {
  670. #ifdef COUNT_PROJECT_TESTS
  671.         Project_Tests++;
  672. #endif
  673.  
  674.         if ((x >= Node->Project.x1) && (x <= Node->Project.x2))
  675.         {
  676. #ifdef COUNT_PROJECT_TESTS
  677.           Project_Tests_Succeeded++;
  678. #endif
  679.  
  680.           /* add node to node queue */
  681.  
  682.           if (size >= MAXQUEUE)
  683.             Fatal_Error("Node queue overflow.\n");
  684.  
  685.           Tree_Node_Queue[size++] = Node;
  686.         }
  687.           }
  688.         }
  689.  
  690.     break;
  691.  
  692.       case TRUE:
  693.  
  694.         /* Unpruned leaf --> test object's bounding box in 3d */
  695.  
  696.         CheckAndEnqueue(Tree_Leaf_Queue, &Qsize, ((PROJECT_TREE_LEAF *)Tree)->Object,
  697.           &((PROJECT_TREE_LEAF *)Tree)->Object->Bounds, &rayinfo);
  698.  
  699.         break;
  700.  
  701.        /* default:
  702.  
  703.         The node/leaf is pruned and needn't be checked */
  704.  
  705.     }
  706.       }
  707.  
  708.       /* Now test the candidates in the priority queue */
  709.  
  710.       while (Qsize > 0)
  711.       {
  712.     PriorityQueueDelete(Tree_Leaf_Queue, &Qsize, &key, &Object);
  713.  
  714.     if (key > Best_Intersection->Depth)
  715.       break;
  716.  
  717.     if (Intersection(&New_Intersection, Object, Ray))
  718.     {
  719.       if (New_Intersection.Depth < Best_Intersection->Depth)
  720.       {
  721.         *Best_Intersection = New_Intersection;
  722.         Found = TRUE;
  723.       }
  724.     }
  725.       }
  726.  
  727.       break;
  728.  
  729.  
  730.  
  731.     /************************************************************************
  732.     * Use bounding slab tests for all nodes that pass the projection test.
  733.     *************************************************************************/
  734.  
  735.     case PROJECTIONS_WITH_NODE_SLABS :
  736.  
  737.       /* Create the direction vectors for this ray */
  738.  
  739.       Create_Rayinfo(Ray, &rayinfo);
  740.  
  741.       /* Check root */
  742.  
  743. #ifdef COUNT_PROJECT_TESTS
  744.       Project_Tests++;
  745. #endif
  746.  
  747.       if ((x >= Tree->Project.x1) && (x <= Tree->Project.x2))
  748.       {
  749. #ifdef COUNT_PROJECT_TESTS
  750.     Project_Tests_Succeeded++;
  751. #endif
  752.  
  753.     CheckAndEnqueue(Tree_Leaf_Queue, &Qsize, (OBJECT *)Tree,
  754.       &Tree->Object->Bounds, &rayinfo);
  755.       }
  756.  
  757.       while (Qsize > 0)
  758.       {
  759.     PriorityQueueDelete(Tree_Leaf_Queue, &Qsize, &key, &Object);
  760.  
  761.     if (key > Best_Intersection->Depth)
  762.       break;
  763.  
  764.     Tree = (PROJECT_TREE_NODE *)Object;
  765.  
  766.     switch (Tree->is_leaf)
  767.     {
  768.       case FALSE:
  769.  
  770.         /* Check siblings of the unpruned node in 2d */
  771.  
  772.         for (i = 0; i < Tree->Entries; i++)
  773.         {
  774.           Node = Tree->Entry[i];
  775.  
  776.           /* Check unpruned siblings only */
  777.  
  778.           if (Node->is_leaf < PRUNE_CHECK)
  779.           {
  780. #ifdef COUNT_PROJECT_TESTS
  781.         Project_Tests++;
  782. #endif
  783.  
  784.         if ((x >= Node->Project.x1) && (x <= Node->Project.x2))
  785.         {
  786. #ifdef COUNT_PROJECT_TESTS
  787.           Project_Tests_Succeeded++;
  788. #endif
  789.  
  790.           CheckAndEnqueue(Tree_Leaf_Queue, &Qsize, (OBJECT *)Node,
  791.             &Node->Object->Bounds, &rayinfo);
  792.         }
  793.           }
  794.         }
  795.  
  796.         break;
  797.  
  798.       case TRUE:
  799.  
  800.         /* Unpruned leaf --> test object */
  801.  
  802.         if (Intersection(&New_Intersection, ((PROJECT_TREE_LEAF *)Tree)->Object, Ray))
  803.         {
  804.           if (New_Intersection.Depth < Best_Intersection->Depth)
  805.           {
  806.         *Best_Intersection = New_Intersection;
  807.         Found = TRUE;
  808.           }
  809.         }
  810.  
  811.         break;
  812.  
  813.        /* default:
  814.  
  815.         The node/leaf is pruned and needn't be checked */
  816.  
  817.     }
  818.       }
  819.  
  820.       break;
  821.  
  822.  
  823.  
  824.     default :
  825.       Fatal_Error("Unkown algorithm.\n");
  826.   }
  827.  
  828.   return(Found);
  829. }
  830.  
  831.  
  832.  
  833. /*****************************************************************************
  834. *
  835. * FUNCTION      : Intersect_Light_Tree
  836. *
  837. * ARGUMENTS     : Ray               - Shadow ray
  838. *                 Tree              - Light tree's top-node
  839. *                 x                 - X-coordinate of the shadow ray
  840. *                 y                 - Y-coordinate of the shadow ray
  841. *                 Best_Intersection - Intersection found
  842. *                 Best_Object       - Object found
  843. *
  844. * MODIFIED ARGS : Best_Intersection, Best_Object
  845. *
  846. * RETURN VALUE  : none
  847. *
  848. * AUTHOR        : Dieter Bayer, May 1994
  849. *
  850. * DESCRIPTION
  851. *
  852. *   Intersect a shadow ray with the light tree
  853. *   (same as for the vista tree but without pruning).
  854. *
  855. * CHANGES
  856. *
  857. *   -
  858. *
  859. ******************************************************************************/
  860.  
  861. int Intersect_Light_Tree(Ray, Tree, x, y, Best_Intersection, Best_Object)
  862. RAY *Ray;
  863. PROJECT_TREE_NODE *Tree;
  864. int x, y;
  865. INTERSECTION *Best_Intersection;
  866. OBJECT **Best_Object;
  867. {
  868.   INTERSECTION New_Intersection;
  869.   unsigned short i;
  870.   unsigned Qsize, size;
  871.   int Found;
  872.   RAYINFO rayinfo;
  873.   DBL key;
  874.   OBJECT *Object;
  875.   PROJECT_TREE_NODE *Node;
  876.  
  877.   /* Start with an empty priority queue */
  878.  
  879.   Qsize = 0;
  880.  
  881.   Found = FALSE;
  882.  
  883.   totalQueueResets++;
  884.  
  885.   /* which algorithm to use? */
  886.  
  887.   switch (Project_Algorithm)
  888.   {
  889.     /************************************************************************
  890.     * Do not use any bounding slab tests. just use their projections.
  891.     *************************************************************************/
  892.  
  893.     case PROJECTIONS_WITHOUT_SLABS :
  894.  
  895.       /* Check root */
  896.  
  897. #ifdef COUNT_PROJECT_TESTS
  898.       Project_Tests++;
  899. #endif
  900.  
  901.       if ((x >= Tree->Project.x1) && (x <= Tree->Project.x2) &&
  902.       (y >= Tree->Project.y1) && (y <= Tree->Project.y2))
  903.       {
  904. #ifdef COUNT_PROJECT_TESTS
  905.     Project_Tests_Succeeded++;
  906. #endif
  907.  
  908.     Tree_Node_Queue[Qsize++] = Tree;
  909.       }
  910.  
  911.       while (Qsize > 0)
  912.       {
  913.     Tree = Tree_Node_Queue[--Qsize];
  914.  
  915.     if (Tree->is_leaf)
  916.     {
  917.       /* Leaf --> test object */
  918.  
  919.       if (Intersection(&New_Intersection, ((PROJECT_TREE_LEAF *)Tree)->Object, Ray))
  920.       {
  921.         if (New_Intersection.Depth < Best_Intersection->Depth)
  922.         {
  923.           *Best_Intersection = New_Intersection;
  924.           *Best_Object = ((PROJECT_TREE_LEAF *)Tree)->Object;
  925.           Found = TRUE;
  926.         }
  927.       }
  928.     }
  929.     else
  930.     {
  931.       /* Check siblings of the node in 2d */
  932.  
  933.       for (i = 0; i < Tree->Entries; i++)
  934.       {
  935.         Node = Tree->Entry[i];
  936.  
  937. #ifdef COUNT_PROJECT_TESTS
  938.         Project_Tests++;
  939. #endif
  940.  
  941.         if ((x >= Node->Project.x1) && (x <= Node->Project.x2) &&
  942.         (y >= Node->Project.y1) && (y <= Node->Project.y2))
  943.         {
  944. #ifdef COUNT_PROJECT_TESTS
  945.           Project_Tests_Succeeded++;
  946. #endif
  947.  
  948.           /* Add node to node queue */
  949.  
  950.           if (Qsize >= MAXQUEUE)
  951.         Fatal_Error("Node queue overflow.\n");
  952.  
  953.           Tree_Node_Queue[Qsize++] = Node;
  954.         }
  955.       }
  956.     }
  957.       }
  958.  
  959.       break;
  960.  
  961.  
  962.  
  963.     /************************************************************************
  964.     * Use bounding slab tests for leaves (i.e. objects) in the tree.
  965.     *************************************************************************/
  966.  
  967.     case PROJECTIONS_WITH_LEAF_SLABS :
  968.  
  969.       /* Create the direction vectors for this ray */
  970.  
  971.       Create_Rayinfo(Ray, &rayinfo);
  972.  
  973.       /* Fill the priority queue with all possible candidates */
  974.  
  975.       size = 0;
  976.  
  977.       /* Check root */
  978.  
  979. #ifdef COUNT_PROJECT_TESTS
  980.       Project_Tests++;
  981. #endif
  982.  
  983.       if ((x >= Tree->Project.x1) && (x <= Tree->Project.x2) &&
  984.       (y >= Tree->Project.y1) && (y <= Tree->Project.y2))
  985.       {
  986. #ifdef COUNT_PROJECT_TESTS
  987.     Project_Tests_Succeeded++;
  988. #endif
  989.  
  990.     Tree_Node_Queue[size++] = Tree;
  991.       }
  992.  
  993.       while (size > 0)
  994.       {
  995.     Tree = Tree_Node_Queue[--size];
  996.  
  997.     if (Tree->is_leaf)
  998.     {
  999.       /* Leaf --> test object's bounding box in 3d */
  1000.  
  1001.       CheckAndEnqueue(Tree_Leaf_Queue, &Qsize, ((PROJECT_TREE_LEAF *)Tree)->Object,
  1002.         &((PROJECT_TREE_LEAF *)Tree)->Object->Bounds, &rayinfo);
  1003.     }
  1004.     else
  1005.     {
  1006.       /* Check siblings of the node in 2d */
  1007.  
  1008.       for (i = 0; i < Tree->Entries; i++)
  1009.       {
  1010.         Node = Tree->Entry[i];
  1011.  
  1012. #ifdef COUNT_PROJECT_TESTS
  1013.         Project_Tests++;
  1014. #endif
  1015.  
  1016.         if ((x >= Node->Project.x1) && (x <= Node->Project.x2) &&
  1017.         (y >= Node->Project.y1) && (y <= Node->Project.y2))
  1018.         {
  1019. #ifdef COUNT_PROJECT_TESTS
  1020.           Project_Tests_Succeeded++;
  1021. #endif
  1022.  
  1023.           /* Add node to node queue */
  1024.  
  1025.           if (size >= MAXQUEUE)
  1026.         Fatal_Error("Node queue overflow.\n");
  1027.  
  1028.           Tree_Node_Queue[size++] = Node;
  1029.         }
  1030.       }
  1031.     }
  1032.       }
  1033.  
  1034.       /* Now test the candidates in the priority queue */
  1035.  
  1036.       while (Qsize > 0)
  1037.       {
  1038.     PriorityQueueDelete(Tree_Leaf_Queue, &Qsize, &key, &Object);
  1039.  
  1040.     if (key > Best_Intersection->Depth)
  1041.       break;
  1042.  
  1043.     if (Intersection(&New_Intersection, Object, Ray))
  1044.     {
  1045.       if (New_Intersection.Depth < Best_Intersection->Depth)
  1046.       {
  1047.         *Best_Intersection = New_Intersection;
  1048.         *Best_Object = Object;
  1049.         Found = TRUE;
  1050.       }
  1051.     }
  1052.       }
  1053.  
  1054.       break;
  1055.  
  1056.  
  1057.  
  1058.     /************************************************************************
  1059.     * Use bounding slab tests for all nodes that pass the projection test.
  1060.     *************************************************************************/
  1061.  
  1062.     case PROJECTIONS_WITH_NODE_SLABS :
  1063.  
  1064.       /* Create the direction vectors for this ray */
  1065.  
  1066.       Create_Rayinfo(Ray, &rayinfo);
  1067.  
  1068.       /* Check root */
  1069.  
  1070. #ifdef COUNT_PROJECT_TESTS
  1071.       Project_Tests++;
  1072. #endif
  1073.  
  1074.       if ((x >= Tree->Project.x1) && (x <= Tree->Project.x2) &&
  1075.       (y >= Tree->Project.y1) && (y <= Tree->Project.y2))
  1076.       {
  1077. #ifdef COUNT_PROJECT_TESTS
  1078.     Project_Tests_Succeeded++;
  1079. #endif
  1080.  
  1081.     CheckAndEnqueue(Tree_Leaf_Queue, &Qsize, (OBJECT *)Tree,
  1082.       &Tree->Object->Bounds, &rayinfo);
  1083.       }
  1084.  
  1085.       while (Qsize > 0)
  1086.       {
  1087.     PriorityQueueDelete(Tree_Leaf_Queue, &Qsize, &key, &Object);
  1088.  
  1089.     if (key > Best_Intersection->Depth)
  1090.       break;
  1091.  
  1092.     Tree = (PROJECT_TREE_NODE *)Object;
  1093.  
  1094.     if (Tree->is_leaf)
  1095.     {
  1096.       /* Leaf --> test object */
  1097.  
  1098.       if (Intersection(&New_Intersection, ((PROJECT_TREE_LEAF *)Tree)->Object, Ray))
  1099.       {
  1100.         if (New_Intersection.Depth < Best_Intersection->Depth)
  1101.         {
  1102.           *Best_Intersection = New_Intersection;
  1103.           *Best_Object = ((PROJECT_TREE_LEAF *)Tree)->Object;
  1104.           Found = TRUE;
  1105.         }
  1106.       }
  1107.     }
  1108.     else
  1109.     {
  1110.       /* Check siblings of the unpruned node in 2d */
  1111.  
  1112.       for (i = 0; i < Tree->Entries; i++)
  1113.       {
  1114.         Node = Tree->Entry[i];
  1115.  
  1116. #ifdef COUNT_PROJECT_TESTS
  1117.         Project_Tests++;
  1118. #endif
  1119.  
  1120.         if ((x >= Node->Project.x1) && (x <= Node->Project.x2) &&
  1121.         (y >= Node->Project.y1) && (y <= Node->Project.y2))
  1122.         {
  1123. #ifdef COUNT_PROJECT_TESTS
  1124.           Project_Tests_Succeeded++;
  1125. #endif
  1126.  
  1127.           CheckAndEnqueue(Tree_Leaf_Queue, &Qsize, (OBJECT *)Node,
  1128.         &Node->Object->Bounds, &rayinfo);
  1129.         }
  1130.       }
  1131.     }
  1132.       }
  1133.  
  1134.       break;
  1135.  
  1136.  
  1137.  
  1138.     default :
  1139.       Fatal_Error("Unkown algorithm.\n");
  1140.   }
  1141.  
  1142.   return(Found);
  1143. }
  1144.  
  1145.  
  1146.  
  1147. /*****************************************************************************
  1148. *
  1149. * FUNCTION      : Project_triangle
  1150. *
  1151. * ARGUMENTS     : Project    - Triangle's projection
  1152. *                 P1, P2, P3 - Triangle's edges
  1153. *                 visible    - Flag if triangle is visible
  1154. *
  1155. * MODIFIED ARGS : Project, visible
  1156. *
  1157. * RETURN VALUE  : none
  1158. *
  1159. * AUTHOR        : Dieter Bayer, May 1994
  1160. *
  1161. * DESCRIPTION
  1162. *
  1163. *   Project a triangle onto the screen.
  1164. *
  1165. * CHANGES
  1166. *
  1167. *   -
  1168. *
  1169. ******************************************************************************/
  1170.  
  1171. static void Project_triangle (Project, P1, P2, P3, visible)
  1172. PROJECT *Project;
  1173. VECTOR P1, P2, P3;
  1174. int *visible;
  1175. {
  1176.   VECTOR Points[MAX_CLIP_POINTS];
  1177.   int i, number;
  1178.   int x, y;
  1179.  
  1180.   Points[0] = P1;
  1181.   Points[1] = P2;
  1182.   Points[2] = P3;
  1183.  
  1184.   number = 3;
  1185.  
  1186.   /* Clip triangle only if some quick tests say it's necessary.
  1187.      Assuming that only a few triangles need clipping this saves some time.
  1188.      (I don't need to write fabs(1+P?.z) since the tests succeed anyway if
  1189.       P?.z < -1. Hope the compiler doesn't change the tests' order!) */
  1190.  
  1191.   if ((P1.z < -1.0) || (P2.z < -1.0) || (P3.z < -1.0) ||
  1192.       (fabs(P1.x) > 0.5*(1.0+P1.z)) || (fabs(P1.y) > 0.5*(1.0+P1.z)) ||
  1193.       (fabs(P2.x) > 0.5*(1.0+P2.z)) || (fabs(P2.y) > 0.5*(1.0+P2.z)) ||
  1194.       (fabs(P3.x) > 0.5*(1.0+P3.z)) || (fabs(P3.y) > 0.5*(1.0+P3.z)))
  1195.   {
  1196.     Clip_Polygon(Points, &number, &VIEW_VX1, &VIEW_VX2, &VIEW_VY1, &VIEW_VY2,
  1197.                    VIEW_DX1,  VIEW_DX2,  VIEW_DY1,  VIEW_DY2);
  1198.   }
  1199.  
  1200.   if (!number)
  1201.     return;
  1202.  
  1203.   for (i = 0; i < number; i++)
  1204.   {
  1205.     if (Points[i].z == -1.0)
  1206.     {
  1207.       Points[i].x = Points[i].y = 0.0;
  1208.     }
  1209.     else
  1210.     {
  1211.       Points[i].x = Points[i].x / (1.0 + Points[i].z);
  1212.       Points[i].y = Points[i].y / (1.0 + Points[i].z);
  1213.     }
  1214.  
  1215.     x = Frame.Screen_Width/2  + (int)(Frame.Screen_Width  * Points[i].x);
  1216.     y = Frame.Screen_Height/2 - (int)(Frame.Screen_Height * Points[i].y);
  1217.  
  1218.     if (x < Project->x1) Project->x1 = x;
  1219.     if (x > Project->x2) Project->x2 = x;
  1220.     if (y < Project->y1) Project->y1 = y;
  1221.     if (y > Project->y2) Project->y2 = y;
  1222.   }
  1223.  
  1224.   *visible = TRUE;
  1225. }
  1226.  
  1227.  
  1228.  
  1229. /*****************************************************************************
  1230. *
  1231. * FUNCTION      : Project_rectangle
  1232. *
  1233. * ARGUMENTS     : Project        - Rectangle's projection
  1234. *                 P1, P2, P3, P4 - Rectangle's edges
  1235. *                 visible        - Flag if rectangle is visible
  1236. *
  1237. * MODIFIED ARGS : Project, visible
  1238. *
  1239. * RETURN VALUE  : none
  1240. *
  1241. * AUTHOR        : Dieter Bayer, May 1994
  1242. *
  1243. * DESCRIPTION
  1244. *
  1245. *   Project a rectangle onto the screen.
  1246. *
  1247. * CHANGES
  1248. *
  1249. *   -
  1250. *
  1251. ******************************************************************************/
  1252.  
  1253. static void Project_rectangle(Project, P1, P2, P3, P4, visible)
  1254. PROJECT *Project;
  1255. VECTOR P1, P2, P3, P4;
  1256. int *visible;
  1257. {
  1258.   VECTOR Points[MAX_CLIP_POINTS];
  1259.   int i, number;
  1260.   int x, y;
  1261.  
  1262.   Points[0] = P1;
  1263.   Points[1] = P2;
  1264.   Points[2] = P3;
  1265.   Points[3] = P4;
  1266.  
  1267.   number = 4;
  1268.  
  1269.   /* Clip square only if some quick tests say it's necessary.
  1270.      Assuming that only a few squares need clipping this saves some time.
  1271.      (I don't need to write fabs(1+P?.z) since the tests succeed anyway if
  1272.       P?.z < -1. Hope the compiler doesn't change the tests' order!) */
  1273.  
  1274.   if ((P1.z < -1.0) || (P2.z < -1.0) || (P3.z < -1.0) || (P4.z < -1.0) ||
  1275.       (fabs(P1.x) > 0.5*(1.0+P1.z)) || (fabs(P1.y) > 0.5*(1.0+P1.z)) ||
  1276.       (fabs(P2.x) > 0.5*(1.0+P2.z)) || (fabs(P2.y) > 0.5*(1.0+P2.z)) ||
  1277.       (fabs(P3.x) > 0.5*(1.0+P3.z)) || (fabs(P3.y) > 0.5*(1.0+P3.z)) ||
  1278.       (fabs(P4.x) > 0.5*(1.0+P4.z)) || (fabs(P4.y) > 0.5*(1.0+P4.z)))
  1279.   {
  1280.     Clip_Polygon(Points, &number, &VIEW_VX1, &VIEW_VX2, &VIEW_VY1, &VIEW_VY2,
  1281.                    VIEW_DX1,  VIEW_DX2,  VIEW_DY1,  VIEW_DY2);
  1282.   }
  1283.  
  1284.   if (!number)
  1285.     return;
  1286.  
  1287.   for (i = 0; i < number; i++)
  1288.   {
  1289.     if (Points[i].z == -1.0)
  1290.     {
  1291.       Points[i].x = Points[i].y = 0.0;
  1292.     }
  1293.     else
  1294.     {
  1295.       Points[i].x = Points[i].x / (1.0 + Points[i].z);
  1296.       Points[i].y = Points[i].y / (1.0 + Points[i].z);
  1297.     }
  1298.  
  1299.     x = Frame.Screen_Width/2  + (int)(Frame.Screen_Width  * Points[i].x);
  1300.     y = Frame.Screen_Height/2 - (int)(Frame.Screen_Height * Points[i].y);
  1301.  
  1302.     if (x < Project->x1) Project->x1 = x;
  1303.     if (x > Project->x2) Project->x2 = x;
  1304.     if (y < Project->y1) Project->y1 = y;
  1305.     if (y > Project->y2) Project->y2 = y;
  1306.   }
  1307.  
  1308.   *visible = TRUE;
  1309. }
  1310.  
  1311.  
  1312.  
  1313.  
  1314. /*****************************************************************************
  1315. *
  1316. * FUNCTION      : Project_BBox
  1317. *
  1318. * ARGUMENTS     : Project - Box's projection
  1319. *                 Points  - Box's edges
  1320. *                 visible - Flag if box is visible
  1321. *
  1322. * MODIFIED ARGS : Project, visible
  1323. *
  1324. * RETURN VALUE  : none
  1325. *
  1326. * AUTHOR        : Dieter Bayer, May 1994
  1327. *
  1328. * DESCRIPTION
  1329. *
  1330. *   Project a box onto the screen.
  1331. *
  1332. * CHANGES
  1333. *
  1334. *   -
  1335. *
  1336. ******************************************************************************/
  1337.  
  1338. static void Project_Bbox(Project, Points, visible)
  1339. PROJECT *Project;
  1340. VECTOR *Points;
  1341. int *visible;
  1342. {
  1343.   int vis;
  1344.   PROJECT New;
  1345.  
  1346.   New.x1 = MAX_VB_ENTRY;
  1347.   New.x2 = MIN_VB_ENTRY;
  1348.   New.y1 = MAX_VB_ENTRY;
  1349.   New.y2 = MIN_VB_ENTRY;
  1350.  
  1351.   vis = FALSE;
  1352.  
  1353.   Project_rectangle(&New, Points[0], Points[1], Points[3], Points[2], &vis);
  1354.   Project_rectangle(&New, Points[4], Points[5], Points[7], Points[6], &vis);
  1355.   Project_rectangle(&New, Points[0], Points[1], Points[5], Points[4], &vis);
  1356.   Project_rectangle(&New, Points[2], Points[3], Points[7], Points[6], &vis);
  1357.   Project_rectangle(&New, Points[1], Points[3], Points[7], Points[5], &vis);
  1358.   Project_rectangle(&New, Points[0], Points[2], Points[6], Points[4], &vis);
  1359.  
  1360.   if (vis)
  1361.   {
  1362.     if (New.x1 > Project->x1) Project->x1 = New.x1;
  1363.     if (New.x2 < Project->x2) Project->x2 = New.x2;
  1364.     if (New.y1 > Project->y1) Project->y1 = New.y1;
  1365.     if (New.y2 < Project->y2) Project->y2 = New.y2;
  1366.     *visible = TRUE;
  1367.   }
  1368. }
  1369.  
  1370.  
  1371.  
  1372. /*****************************************************************************
  1373. *
  1374. * FUNCTION      : Project_Bounds
  1375. *
  1376. * ARGUMENTS     : Project - Bounding box's projection
  1377. *                 Bounds  - Bounding box
  1378. *                 visible - Flag if bounding box is visible
  1379. *
  1380. * MODIFIED ARGS : Project, visible
  1381. *
  1382. * RETURN VALUE  : none
  1383. *
  1384. * AUTHOR        : Dieter Bayer, May 1994
  1385. *
  1386. * DESCRIPTION
  1387. *
  1388. *   Project a bounding box onto the screen.
  1389. *
  1390. * CHANGES
  1391. *
  1392. *   -
  1393. *
  1394. ******************************************************************************/
  1395.  
  1396. static void Project_Bounds(Project, Bounds, visible)
  1397. PROJECT *Project;
  1398. BBOX *Bounds;
  1399. int *visible;
  1400. {
  1401.   int i;
  1402.   VECTOR P[8];
  1403.  
  1404.   for (i = 0; i<8; i++)
  1405.   {
  1406.     P[i] = Bounds->Lower_Left;
  1407.  
  1408.     P[i].x += ((i & 1) ? Bounds->Lengths.x : 0.0);
  1409.     P[i].y += ((i & 2) ? Bounds->Lengths.y : 0.0);
  1410.     P[i].z += ((i & 4) ? Bounds->Lengths.z : 0.0);
  1411.  
  1412.     Transform_Point (&P[i]);
  1413.   }
  1414.  
  1415.   Project_Bbox(Project, &P[0], visible);
  1416. }
  1417.  
  1418.  
  1419.  
  1420. /*****************************************************************************
  1421. *
  1422. * FUNCTION      : Project_Bicubic_Patch
  1423. *
  1424. * ARGUMENTS     : Project - Projection
  1425. *                 Object  - Object
  1426. *
  1427. * MODIFIED ARGS : Project
  1428. *
  1429. * RETURN VALUE  : none
  1430. *
  1431. * AUTHOR        : Dieter Bayer, May 1994
  1432. *
  1433. * DESCRIPTION
  1434. *
  1435. *   Project the bounding sphere of a bicubic patch onto the screen.
  1436. *
  1437. * CHANGES
  1438. *
  1439. *   -
  1440. *
  1441. ******************************************************************************/
  1442.  
  1443. static void Project_Bicubic_Patch(Project, Object)
  1444. PROJECT *Project;
  1445. OBJECT *Object;
  1446. {
  1447.   BICUBIC_PATCH *patch;
  1448.   DBL x, y, z, r, a20, a02, a11, a10, a01, a00;
  1449.   MATRIX A;
  1450.  
  1451.   patch = (BICUBIC_PATCH *)Object;
  1452.  
  1453.   /* Set up 4x4 quadric matrix A */
  1454.  
  1455.   x = patch->Bounding_Sphere_Center.x;
  1456.   y = patch->Bounding_Sphere_Center.y;
  1457.   z = patch->Bounding_Sphere_Center.z;
  1458.  
  1459.   r = 1.0 / (patch->Bounding_Sphere_Radius * patch->Bounding_Sphere_Radius);
  1460.  
  1461.   A[0][0] = r;    A[0][1] = 0.0;  A[0][2] = 0.0;  A[0][3] = -x*r;
  1462.   A[1][0] = 0.0;  A[1][1] = r;    A[1][2] = 0.0;  A[1][3] = -y*r;
  1463.   A[2][0] = 0.0;  A[2][1] = 0.0;  A[2][2] = r;    A[2][3] = -z*r;
  1464.   A[3][0] = -x*r; A[3][1] = -y*r; A[3][2] = -z*r; A[3][3] = r*(x*x+y*y+z*z) - 1.0;
  1465.  
  1466.   Project_Vista(&A, NULL, &a20, &a02, &a11, &a10, &a01, &a00);
  1467.  
  1468.   /* Get vista's bounding rectangle */
  1469.  
  1470.   Get_Ellipse_Projection(Project, a20, a02, a11, a10, a01, a00);
  1471. }
  1472.  
  1473.  
  1474.  
  1475. /*****************************************************************************
  1476. *
  1477. * FUNCTION      : Project_Box
  1478. *
  1479. * ARGUMENTS     : Project - Projection
  1480. *                 Object  - Object
  1481. *                 visible - Flag if object is visible
  1482. *
  1483. * MODIFIED ARGS : Project, visible
  1484. *
  1485. * RETURN VALUE  : none
  1486. *
  1487. * AUTHOR        : Dieter Bayer, May 1994
  1488. *
  1489. * DESCRIPTION
  1490. *
  1491. *   Project a box onto the screen.
  1492. *
  1493. * CHANGES
  1494. *
  1495. *   -
  1496. *
  1497. ******************************************************************************/
  1498.  
  1499. static void Project_Box(Project, Object, visible)
  1500. PROJECT *Project;
  1501. OBJECT *Object;
  1502. int *visible;
  1503. {
  1504.   int i;
  1505.   VECTOR P[8];
  1506.   BOX *box;
  1507.  
  1508.   box = (BOX *)Object;
  1509.  
  1510.   for (i = 0; i<8; i++)
  1511.   {
  1512.     P[i] = box->bounds[0];
  1513.  
  1514.     if (i & 1) P[i].x = box->bounds[1].x;
  1515.     if (i & 2) P[i].y = box->bounds[1].y;
  1516.     if (i & 4) P[i].z = box->bounds[1].z;
  1517.  
  1518.     if (box->Trans != NULL)
  1519.       MTransPoint(&P[i], &P[i], box->Trans);
  1520.  
  1521.     Transform_Point (&P[i]);
  1522.   }
  1523.  
  1524.   Project_Bbox(Project, &P[0], visible);
  1525. }
  1526.  
  1527.  
  1528.  
  1529. /*****************************************************************************
  1530. *
  1531. * FUNCTION      : Project_Height_Field
  1532. *
  1533. * ARGUMENTS     : Project - Projection
  1534. *                 Object  - Object
  1535. *                 visible - Flag if object is visible
  1536. *
  1537. * MODIFIED ARGS : Project, visible
  1538. *
  1539. * RETURN VALUE  : none
  1540. *
  1541. * AUTHOR        : Dieter Bayer, May 1994
  1542. *
  1543. * DESCRIPTION
  1544. *
  1545. *   Project the bounding box of a height field onto the screen.
  1546. *
  1547. * CHANGES
  1548. *
  1549. *   -
  1550. *
  1551. ******************************************************************************/
  1552.  
  1553. static void Project_Height_Field(Project, Object, visible)
  1554. PROJECT *Project;
  1555. OBJECT *Object;
  1556. int *visible;
  1557. {
  1558.   int i;
  1559.   VECTOR P[8];
  1560.   HEIGHT_FIELD *hfield;
  1561.  
  1562.   hfield = (HEIGHT_FIELD *)Object;
  1563.  
  1564.   for (i = 0; i<8; i++)
  1565.   {
  1566.     P[i] = hfield->bounding_box->bounds[0];
  1567.  
  1568.     if (i & 1) P[i].x = hfield->bounding_box->bounds[1].x;
  1569.     if (i & 2) P[i].y = hfield->bounding_box->bounds[1].y;
  1570.     if (i & 4) P[i].z = hfield->bounding_box->bounds[1].z;
  1571.  
  1572.     if (hfield->Trans != NULL)
  1573.       MTransPoint(&P[i], &P[i], hfield->Trans);
  1574.  
  1575.     Transform_Point (&P[i]);
  1576.   }
  1577.  
  1578.   Project_Bbox(Project, &P[0], visible);
  1579. }
  1580.  
  1581.  
  1582.  
  1583. /*****************************************************************************
  1584. *
  1585. * FUNCTION      : Project_Triangle
  1586. *
  1587. * ARGUMENTS     : Project - Projection
  1588. *                 Object  - Object
  1589. *                 visible - Flag if object is visible
  1590. *
  1591. * MODIFIED ARGS : Project, visible
  1592. *
  1593. * RETURN VALUE  : none
  1594. *
  1595. * AUTHOR        : Dieter Bayer, May 1994
  1596. *
  1597. * DESCRIPTION
  1598. *
  1599. *   Project a triangle onto the screen.
  1600. *
  1601. * CHANGES
  1602. *
  1603. *   -
  1604. *
  1605. ******************************************************************************/
  1606.  
  1607. static void Project_Triangle(Project, Object, visible)
  1608. PROJECT *Project;
  1609. OBJECT *Object;
  1610. int *visible;
  1611. {
  1612.   int i, vis;
  1613.   VECTOR P[3];
  1614.   PROJECT New;
  1615.  
  1616.   New.x1 = MAX_VB_ENTRY;
  1617.   New.x2 = MIN_VB_ENTRY;
  1618.   New.y1 = MAX_VB_ENTRY;
  1619.   New.y2 = MIN_VB_ENTRY;
  1620.  
  1621.   P[0] = ((TRIANGLE *)Object)->P1;
  1622.   P[1] = ((TRIANGLE *)Object)->P2;
  1623.   P[2] = ((TRIANGLE *)Object)->P3;
  1624.  
  1625.   for (i = 0; i < 3; i++)
  1626.   {
  1627.     Transform_Point(&P[i]);
  1628.   }
  1629.  
  1630.   vis = FALSE;
  1631.  
  1632.   Project_triangle(&New, P[0], P[1], P[2], &vis);
  1633.  
  1634.   if (vis)
  1635.   {
  1636.     if (New.x1 > Project->x1) Project->x1 = New.x1;
  1637.     if (New.x2 < Project->x2) Project->x2 = New.x2;
  1638.     if (New.y1 > Project->y1) Project->y1 = New.y1;
  1639.     if (New.y2 < Project->y2) Project->y2 = New.y2;
  1640.     *visible = TRUE;
  1641.   }
  1642. }
  1643.  
  1644.  
  1645.  
  1646. /*****************************************************************************
  1647. *
  1648. * FUNCTION      : Project_Smooth_Triangle
  1649. *
  1650. * ARGUMENTS     : Project - Projection
  1651. *                 Object  - Object
  1652. *                 visible - Flag if object is visible
  1653. *
  1654. * MODIFIED ARGS : Project, visible
  1655. *
  1656. * RETURN VALUE  : none
  1657. *
  1658. * AUTHOR        : Dieter Bayer, May 1994
  1659. *
  1660. * DESCRIPTION
  1661. *
  1662. *   Project a smooth triangle onto the screen.
  1663. *
  1664. * CHANGES
  1665. *
  1666. *   -
  1667. *
  1668. ******************************************************************************/
  1669.  
  1670. static void Project_Smooth_Triangle(Project, Object, visible)
  1671. PROJECT *Project;
  1672. OBJECT *Object;
  1673. int *visible;
  1674. {
  1675.   int i, vis;
  1676.   VECTOR P[3];
  1677.   PROJECT New;
  1678.  
  1679.   New.x1 = MAX_VB_ENTRY;
  1680.   New.x2 = MIN_VB_ENTRY;
  1681.   New.y1 = MAX_VB_ENTRY;
  1682.   New.y2 = MIN_VB_ENTRY;
  1683.  
  1684.   P[0] = ((SMOOTH_TRIANGLE *)Object)->P1;
  1685.   P[1] = ((SMOOTH_TRIANGLE *)Object)->P2;
  1686.   P[2] = ((SMOOTH_TRIANGLE *)Object)->P3;
  1687.  
  1688.   for (i = 0; i < 3; i++)
  1689.   {
  1690.     Transform_Point(&P[i]);
  1691.   }
  1692.  
  1693.   vis = FALSE;
  1694.  
  1695.   Project_triangle(&New, P[0], P[1], P[2], &vis);
  1696.  
  1697.   if (vis)
  1698.   {
  1699.     if (New.x1 > Project->x1) Project->x1 = New.x1;
  1700.     if (New.x2 < Project->x2) Project->x2 = New.x2;
  1701.     if (New.y1 > Project->y1) Project->y1 = New.y1;
  1702.     if (New.y2 < Project->y2) Project->y2 = New.y2;
  1703.     *visible = TRUE;
  1704.   }
  1705. }
  1706.  
  1707.  
  1708.  
  1709. /*****************************************************************************
  1710. *
  1711. * FUNCTION      : Project_Sphere
  1712. *
  1713. * ARGUMENTS     : Project - Projection
  1714. *                 Object  - Oject
  1715. *
  1716. * MODIFIED ARGS : Project
  1717. *
  1718. * RETURN VALUE  : none
  1719. *
  1720. * AUTHOR        : Dieter Bayer, May 1994
  1721. *
  1722. * DESCRIPTION
  1723. *
  1724. *   Project a sphere onto the screen.
  1725. *
  1726. * CHANGES
  1727. *
  1728. *   -
  1729. *
  1730. ******************************************************************************/
  1731.  
  1732. static void Project_Sphere(Project, Object)
  1733. PROJECT *Project;
  1734. OBJECT *Object;
  1735. {
  1736.   SPHERE *sphere;
  1737.   DBL x, y, z, r, a20, a02, a11, a10, a01, a00;
  1738.   MATRIX A;
  1739.  
  1740.   sphere = (SPHERE *)Object;
  1741.  
  1742.   /* Set up 4x4 quadric matrix A0 */
  1743.  
  1744.   x = sphere->Center.x;
  1745.   y = sphere->Center.y;
  1746.   z = sphere->Center.z;
  1747.  
  1748.   r = 1.0/sphere->Radius_Squared;
  1749.  
  1750.   A[0][0] = r;    A[0][1] = 0.0;  A[0][2] = 0.0;  A[0][3] = -x*r;
  1751.   A[1][0] = 0.0;  A[1][1] = r;    A[1][2] = 0.0;  A[1][3] = -y*r;
  1752.   A[2][0] = 0.0;  A[2][1] = 0.0;  A[2][2] = r;    A[2][3] = -z*r;
  1753.   A[3][0] = -x*r; A[3][1] = -y*r; A[3][2] = -z*r; A[3][3] = r*(x*x+y*y+z*z) - 1.0;
  1754.  
  1755.   Project_Vista(&A, sphere->Trans, &a20, &a02, &a11, &a10, &a01, &a00);
  1756.  
  1757.   /* get vista's bounding rectangle */
  1758.  
  1759.   Get_Ellipse_Projection(Project, a20, a02, a11, a10, a01, a00);
  1760. }
  1761.  
  1762.  
  1763.  
  1764. /*****************************************************************************
  1765. *
  1766. * FUNCTION      : Get_Ellipse_Projection
  1767. *
  1768. * ARGUMENTS     : Project        - Projection
  1769. *                 a20, a02, a11,
  1770. *                 a10, a01, a00  - Parameters of the quadratic curve
  1771. *
  1772. * MODIFIED ARGS : Project
  1773. *
  1774. * RETURN VALUE  : none
  1775. *
  1776. * AUTHOR        : Dieter Bayer, May 1994
  1777. *
  1778. * DESCRIPTION
  1779. *
  1780. *   Get the bounding rectangle around an ellipse, i.e. the
  1781. *   quadratic curve: a20*x*x + a02*y*y + a11*x*y + a10*x + a01*y + a00 = 0
  1782. *
  1783. * CHANGES
  1784. *
  1785. *   -
  1786. *
  1787. ******************************************************************************/
  1788.  
  1789. static void Get_Ellipse_Projection(Project, a20, a02, a11, a10, a01, a00)
  1790. PROJECT *Project;
  1791. DBL a20, a02, a11, a10, a01, a00;
  1792. {
  1793.   int x1i, x2i, y1i, y2i;
  1794.   DBL x1, y1, x2, y2;
  1795.   DBL a, b, c, d, k, k1, k2, k3, k4;
  1796.  
  1797.   x1 = y1 = -0.5;
  1798.   x2 = y2 = +0.5;
  1799.  
  1800.   k1 = a11/(-2.0*a20);
  1801.   k2 = a10/(-2.0*a20);
  1802.  
  1803.   k3 = a11/(-2.0*a02);
  1804.   k4 = a01/(-2.0*a02);
  1805.  
  1806.   a = a20 + a02*k3*k3 + a11*k3;
  1807.  
  1808.   b = a10 + 2.0*a02*k3*k4 + a01*k3 + a11*k4;
  1809.  
  1810.   c = a02*k4*k4 + a01*k4 + a00;
  1811.  
  1812.   d = b*b - 4.0*a*c;
  1813.  
  1814.   if (d > 0.0)
  1815.   {
  1816.     a = 2.0*a;
  1817.  
  1818.     d = sqrt(d);
  1819.  
  1820.     x1 = (-b+d)/a;
  1821.     x2 = (-b-d)/a;
  1822.  
  1823.     if (x1>x2)
  1824.     {
  1825.       k = x1; x1 = x2; x2 = k;
  1826.     }
  1827.  
  1828.     a = a02 + a20*k1*k1 + a11*k1;
  1829.  
  1830.     b = a01 + 2.0*a20*k1*k2 + a10*k1 + a11*k2;
  1831.  
  1832.     c = a20*k2*k2 + a10*k2 + a00;
  1833.  
  1834.     d = b*b - 4.0*a*c;
  1835.  
  1836.     if (d > 0.0)
  1837.     {
  1838.       a = 2.0*a;
  1839.  
  1840.       d = sqrt(d);
  1841.  
  1842.       y1 = (-b+d)/a;
  1843.       y2 = (-b-d)/a;
  1844.  
  1845.       if (y1>y2)
  1846.       {
  1847.     k = y1; y1 = y2; y2 = k;
  1848.       }
  1849.     }
  1850.   }
  1851.  
  1852.   if (x1 < -0.5) x1 = -0.5;
  1853.   if (x2 > +0.5) x2 = +0.5;
  1854.   if (y1 < -0.5) y1 = -0.5;
  1855.   if (y2 > +0.5) y2 = +0.5;
  1856.  
  1857.   x1i = Frame.Screen_Width/2 + (int)(Frame.Screen_Width * x1) - 1;
  1858.   x2i = Frame.Screen_Width/2 + (int)(Frame.Screen_Width * x2) + 1;
  1859.  
  1860.   y1i = Frame.Screen_Height/2 - (int)(Frame.Screen_Height * y2) - 1;
  1861.   y2i = Frame.Screen_Height/2 - (int)(Frame.Screen_Height * y1) + 1;
  1862.  
  1863.   if (x1i > Project->x1) Project->x1 = x1i;
  1864.   if (x2i < Project->x2) Project->x2 = x2i;
  1865.  
  1866.   if (y1i > Project->y1) Project->y1 = y1i;
  1867.   if (y2i < Project->y2) Project->y2 = y2i;
  1868. }
  1869.  
  1870.  
  1871.  
  1872. /*****************************************************************************
  1873. *
  1874. * FUNCTION      : Project_Vista
  1875. *
  1876. * ARGUMENTS     : A0             - Matrix defining the quadric surface
  1877. *                 Trans          - Transformation matrices
  1878. *                 a20, a02, a11,
  1879. *                 a10, a01, a00  - Parameters of the projected quadratic curve
  1880. *
  1881. * MODIFIED ARGS : a20, a02, a11, a10, a01, a00
  1882. *
  1883. * RETURN VALUE  : none
  1884. *
  1885. * AUTHOR        : Dieter Bayer, May 1994
  1886. *
  1887. * DESCRIPTION
  1888. *
  1889. *   Project a quadric surface onto the screen (perspective projection)
  1890. *   and get the paramters of the resulting quadratic curve.
  1891. *
  1892. * CHANGES
  1893. *
  1894. *   -
  1895. *
  1896. ******************************************************************************/
  1897.  
  1898. void Project_Vista(A0, Trans, a20, a02, a11, a10, a01, a00)
  1899. MATRIX *A0;
  1900. TRANSFORM *Trans;
  1901. DBL *a20, *a02, *a11, *a10, *a01, *a00;
  1902. {
  1903.   int i, j;
  1904.   MATRIX Tinv, A1, A2, B, Transposed_Matrix;
  1905.   DBL k1, k2, k3;
  1906.  
  1907.   /* Apply object transformations */
  1908.  
  1909.   if (Trans == NULL)
  1910.   {
  1911.     for (i=0;i<4;i++)
  1912.     {
  1913.       for (j=0;j<4;j++)
  1914.       {
  1915.     A1[i][j] = (*A0)[i][j];
  1916.       }
  1917.     }
  1918.   }
  1919.   else
  1920.   {
  1921.     MTranspose(&Transposed_Matrix, &Trans->inverse);
  1922.     MTimes(&A1, &Trans->inverse, A0);
  1923.     MTimes(&A1, &A1, &Transposed_Matrix);
  1924.   }
  1925.  
  1926.   /* Transform into viewing system */
  1927.  
  1928.   MTranspose(&Transposed_Matrix, &WC2VCinv);
  1929.   MTimes(&A2, &Transposed_Matrix, &A1);
  1930.   MTimes(&A2, &A2, &WC2VCinv);
  1931.  
  1932.   /* Calculate quadrics vista */
  1933.  
  1934.   MIdentity(&Tinv);
  1935.  
  1936.   Tinv[3][2] = -1.0;
  1937.  
  1938.   MTranspose(&Transposed_Matrix, &Tinv);
  1939.  
  1940.   MTimes(&B, &Transposed_Matrix, &A2);
  1941.   MTimes(&B, &B, &Tinv);
  1942.  
  1943.   k1 = (B[0][2]+B[2][0])/(-2.0*B[2][2]);
  1944.  
  1945.   k2 = (B[1][2]+B[2][1])/(-2.0*B[2][2]);
  1946.  
  1947.   k3 = (B[2][3]+B[3][2])/(-2.0*B[2][2]);
  1948.  
  1949.   *a20 = B[0][0] + k1*(B[0][2]+B[2][0]) + k1*k1*B[2][2];
  1950.  
  1951.   *a02 = B[1][1] + k2*(B[1][2]+B[2][1]) + k2*k2*B[2][2];
  1952.  
  1953.   *a10 = B[0][3]+B[3][0] + k1*(B[2][3]+B[3][2]) + k3*(B[0][2]+B[2][0]) + 2.0*k1*k3*B[2][2];
  1954.  
  1955.   *a01 = B[1][3]+B[3][1] + k2*(B[2][3]+B[3][2]) + k3*(B[1][2]+B[2][1]) + 2.0*k2*k3*B[2][2];
  1956.  
  1957.   *a11 = B[0][1]+B[1][0] + k1*(B[1][2]+B[2][1]) + k2*(B[0][2]+B[2][0]) + 2.0*k1*k2*B[2][2];
  1958.  
  1959.   *a00 = B[3][3] + k3*(B[2][3]+B[3][2]) + k3*k3*B[2][2];
  1960. }
  1961.  
  1962.  
  1963.  
  1964. /*****************************************************************************
  1965. *
  1966. * FUNCTION      : Transform_Point
  1967. *
  1968. * ARGUMENTS     : P - Point to transform
  1969. *
  1970. * MODIFIED ARGS : P
  1971. *
  1972. * RETURN VALUE  : none
  1973. *
  1974. * AUTHOR        : Dieter Bayer, May 1994
  1975. *
  1976. * DESCRIPTION
  1977. *
  1978. *   Transform a point from the world coordinate system to the viewer's
  1979. *   coordinate system.
  1980. *
  1981. * CHANGES
  1982. *
  1983. *   -
  1984. *
  1985. ******************************************************************************/
  1986.  
  1987. static void Transform_Point(P)
  1988. VECTOR *P;
  1989. {
  1990.   DBL x,y,z;
  1991.  
  1992.   x = P->x - O.x;
  1993.   y = P->y - O.y;
  1994.   z = P->z - O.z;
  1995.  
  1996.   P->x = U.x * x + U.y * y + U.z * z;
  1997.   P->y = V.x * x + V.y * y + V.z * z;
  1998.   P->z = W.x * x + W.y * y + W.z * z;
  1999. }
  2000.  
  2001.  
  2002.  
  2003. /*****************************************************************************
  2004. *
  2005. * FUNCTION      : Init_View_Coordinates
  2006. *
  2007. * ARGUMENTS     : none
  2008. *
  2009. * MODIFIED ARGS : none
  2010. *
  2011. * RETURN VALUE  : none
  2012. *
  2013. * AUTHOR        : Dieter Bayer, May 1994
  2014. *
  2015. * DESCRIPTION
  2016. *
  2017. *   Init the matrices and vectors used to transform a point from
  2018. *   the world coordinate system to the viewer's coordinate system.
  2019. *
  2020. * CHANGES
  2021. *
  2022. *   -
  2023. *
  2024. ******************************************************************************/
  2025.  
  2026. void Init_View_Coordinates()
  2027. {
  2028.   DBL k, up_length, right_length;
  2029.   MATRIX A, B;
  2030.  
  2031.   U = Frame.Camera->Right;
  2032.   V = Frame.Camera->Up;
  2033.   W = Frame.Camera->Direction;
  2034.  
  2035.   VAdd (O, Frame.Camera->Location, Frame.Camera->Direction);
  2036.  
  2037.   VNormalize(U,U);
  2038.   VNormalize(V,V);
  2039.   VNormalize(W,W);
  2040.  
  2041.   VDot(k, U,V);
  2042.   if (fabs(k) > EPSILON)
  2043.     Fatal_Error("Camera: Right-vector not perpendicular to Up-vector.\n");
  2044.  
  2045.   VDot(k, U,W);
  2046.   if (fabs(k) > EPSILON)
  2047.     Fatal_Error("Camera: Right-vector not perpendicular to Direction-vector.\n");
  2048.  
  2049.   VDot(k, V,W);
  2050.   if (fabs(k) > EPSILON)
  2051.     Fatal_Error("Camera: Up-vector not perpendicular to Direction-vector.\n");
  2052.  
  2053.   VLength (distance, Frame.Camera->Direction);
  2054.  
  2055.   VLength (up_length, Frame.Camera->Up);
  2056.   VLength (right_length, Frame.Camera->Right);
  2057.  
  2058.   VScaleEq (U, 1.0/right_length);
  2059.   VScaleEq (V, 1.0/up_length);
  2060.   VScaleEq (W, 1.0/distance);
  2061.  
  2062.   A[0][0] = U.x; A[0][1] = U.y; A[0][2] = U.z; A[0][3] = 0.0;
  2063.   A[1][0] = V.x; A[1][1] = V.y; A[1][2] = V.z; A[1][3] = 0.0;
  2064.   A[2][0] = W.x; A[2][1] = W.y; A[2][2] = W.z; A[2][3] = 0.0;
  2065.   A[3][0] = 0.0; A[3][1] = 0.0; A[3][2] = 0.0; A[3][3] = 1.0;
  2066.  
  2067.   B[0][0] = 1.0; B[0][1] = 0.0; B[0][2] = 0.0; B[0][3] = -O.x;
  2068.   B[1][0] = 0.0; B[1][1] = 1.0; B[1][2] = 0.0; B[1][3] = -O.y;
  2069.   B[2][0] = 0.0; B[2][1] = 0.0; B[2][2] = 1.0; B[2][3] = -O.z;
  2070.   B[3][0] = 0.0; B[3][1] = 0.0; B[3][2] = 0.0; B[3][3] = 1.0;
  2071.  
  2072.   MTimes(&WC2VC, &A, &B);
  2073.   MInvers(&WC2VCinv, &WC2VC);
  2074. }
  2075.  
  2076.  
  2077.  
  2078. /*****************************************************************************
  2079. *
  2080. * FUNCTION      : Get_Perspective_Projection
  2081. *
  2082. * ARGUMENTS     : Object   - Object to project
  2083. *                 Project  - Projection
  2084. *                 infinite - Flag if object is infinite
  2085. *
  2086. * MODIFIED ARGS : Project
  2087. *
  2088. * RETURN VALUE  : none
  2089. *
  2090. * AUTHOR        : Dieter Bayer, May 1994
  2091. *
  2092. * DESCRIPTION
  2093. *
  2094. *   Get the perspective projection of a single object, i.e.
  2095. *   the smallest rectangle enclosing the object's image on the screen.
  2096. *
  2097. * CHANGES
  2098. *
  2099. *   -
  2100. *
  2101. ******************************************************************************/
  2102.  
  2103. static void Get_Perspective_Projection(Object, Project, infinite)
  2104. OBJECT *Object;
  2105. PROJECT *Project;
  2106. int infinite;
  2107. {
  2108.   int visible;
  2109.   METHODS *Methods;
  2110.  
  2111.   visible = FALSE;
  2112.  
  2113.   Methods = Object->Methods;
  2114.  
  2115.   /* If the object is infinite, there's no sense of projecting */
  2116.  
  2117.   if (!infinite)
  2118.   {
  2119.     if ((Methods == &Box_Methods) ||
  2120.     (Methods == &Smooth_Triangle_Methods) ||
  2121.     (Methods == &Triangle_Methods) ||
  2122.     (Methods == &Csg_Height_Field_Methods) ||
  2123.     (Methods == &Height_Field_Methods))
  2124.     {
  2125.       if (Methods == &Box_Methods)
  2126.     Project_Box(Project, Object, &visible);
  2127.  
  2128.       if (Methods == &Csg_Height_Field_Methods)
  2129.     Project_Height_Field(Project, Object, &visible);
  2130.  
  2131.       if (Methods == &Height_Field_Methods)
  2132.     Project_Height_Field(Project, Object, &visible);
  2133.  
  2134.       if (Methods == &Smooth_Triangle_Methods)
  2135.     Project_Smooth_Triangle(Project, Object, &visible);
  2136.  
  2137.       if (Methods == &Triangle_Methods)
  2138.     Project_Triangle(Project, Object, &visible);
  2139.     }
  2140.     else
  2141.     {
  2142.       Project_Bounds(Project, &Object->Bounds, &visible);
  2143.     }
  2144.   }
  2145.  
  2146.   if (visible)
  2147.   {
  2148.     if (Options & ANTIALIAS)
  2149.     {
  2150.       /* Increase the rectangle to make sure that nothing will be missed.
  2151.      For anti-aliased images increase by a larger amount. */
  2152.  
  2153.       Project->x1 = max (0,                     Project->x1 - 2);
  2154.       Project->x2 = min (Frame.Screen_Width-1,  Project->x2 + 2);
  2155.       Project->y1 = max (-1,                    Project->y1 - 2);
  2156.       Project->y2 = min (Frame.Screen_Height-1, Project->y2 + 2);
  2157.     }
  2158.     else
  2159.     {
  2160.       /* Increase the rectangle to make sure that nothing will be missed. */
  2161.  
  2162.       Project->x1 = max (0,                     Project->x1 - 1);
  2163.       Project->x2 = min (Frame.Screen_Width-1,  Project->x2 + 1);
  2164.       Project->y1 = max (0,                     Project->y1 - 1);
  2165.       Project->y2 = min (Frame.Screen_Height-1, Project->y2 + 1);
  2166.     }
  2167.   }
  2168.   else
  2169.   {
  2170.     if (!infinite)
  2171.     {
  2172.       /* Object is invisible (the camera can't see it) */
  2173.  
  2174.       Project->x1 = Project->y1 = MAX_VB_ENTRY;
  2175.       Project->x2 = Project->y2 = MIN_VB_ENTRY;
  2176.     }
  2177.   }
  2178. }
  2179.  
  2180.  
  2181.  
  2182. /*****************************************************************************
  2183. *
  2184. * FUNCTION      : Project_Object
  2185. *
  2186. * ARGUMENTS     : Object   - Object to project
  2187. *                 Project  - Projection
  2188. *
  2189. * MODIFIED ARGS : Project
  2190. *
  2191. * RETURN VALUE  : none
  2192. *
  2193. * AUTHOR        : Dieter Bayer, May 1994
  2194. *
  2195. * DESCRIPTION
  2196. *
  2197. *   Get the projection of a single object depending on the camera
  2198. *   used (perspective/orthographic).
  2199. *
  2200. * CHANGES
  2201. *
  2202. *   -
  2203. *
  2204. ******************************************************************************/
  2205.  
  2206. static void Project_Object(Object, Project)
  2207. OBJECT *Object;
  2208. PROJECT *Project;
  2209. {
  2210.   int infinite;
  2211.   DBL Volume;
  2212.  
  2213.   /* Init project fields, assuming the object is visible! */
  2214.  
  2215.   Project->x1 = Project->y1 = MIN_VB_ENTRY;
  2216.   Project->x2 = Project->y2 = MAX_VB_ENTRY;
  2217.  
  2218.   BOUNDS_VOLUME(Volume, Object->Bounds);
  2219.  
  2220.   infinite = (Volume > INFINITE_VOLUME);
  2221.  
  2222.   Get_Perspective_Projection(Object, Project, infinite);
  2223.  
  2224.   Print_Point(POINT_MOD);
  2225. }
  2226.  
  2227.  
  2228.  
  2229. /*****************************************************************************
  2230. *
  2231. * FUNCTION      : Project_Bounding_Slab
  2232. *
  2233. * ARGUMENTS     : Project  - Projection
  2234. *                 Tree     - Current node/leaf
  2235. *                 Object   - Node/leaf in bounding slab hierarchy
  2236. *
  2237. * MODIFIED ARGS : Project, Tree
  2238. *
  2239. * RETURN VALUE  : none
  2240. *
  2241. * AUTHOR        : Dieter Bayer, May 1994
  2242. *
  2243. * DESCRIPTION
  2244. *
  2245. *   Project the bounding slab hierarchy onto the screen and thus create
  2246. *   the vista buffer hierarchy.
  2247. *
  2248. * CHANGES
  2249. *
  2250. *   -
  2251. *
  2252. ******************************************************************************/
  2253.  
  2254. static void Project_Bounding_Slab(Project, Tree, Object)
  2255. PROJECT *Project;
  2256. PROJECT_TREE_NODE **Tree;
  2257. OBJECT *Object;
  2258. {
  2259.   unsigned short int i;
  2260.   COMPOSITE *Comp;
  2261.   PROJECT Temp;
  2262.   PROJECT_TREE_LEAF *Leaf;
  2263.   PROJECT_TREE_NODE New;
  2264.  
  2265.   if (Object->Type & BOUNDING_OBJECT)
  2266.   {
  2267.     /* Current object is a bounding object, i.e. a node in the slab tree. */
  2268.  
  2269.     Comp = (COMPOSITE *)Object;
  2270.  
  2271.     /* First, init new entry. */
  2272.  
  2273.     New.Entries = 0;
  2274.  
  2275.     New.Object = Object;
  2276.  
  2277.     New.Project.x1 = New.Project.y1 = MAX_VB_ENTRY;
  2278.     New.Project.x2 = New.Project.y2 = MIN_VB_ENTRY;
  2279.  
  2280.     /* Allocate temporary memory for node/leaf entries. */
  2281.  
  2282.     if ((New.Entry = (PROJECT_TREE_NODE **)malloc(Comp->Entries*sizeof(PROJECT_TREE_NODE *))) == NULL)
  2283.     {
  2284.       Fatal_Error("temporary tree entry");
  2285.     }
  2286.  
  2287.     /* This is no leaf, it's a node. */
  2288.  
  2289.     New.is_leaf = FALSE;
  2290.  
  2291.     /* Second, get new entry, i.e. project node's entries. */
  2292.  
  2293.     for (i = 0; i < Comp->Entries; i++)
  2294.     {
  2295.       New.Entry[i] = NULL;
  2296.  
  2297.       Project_Bounding_Slab(&Temp, &New.Entry[New.Entries], Comp->Objects[i]);
  2298.  
  2299.       /* Use only visible entries */
  2300.  
  2301.       if (New.Entry[New.Entries] != NULL)
  2302.       {
  2303.     New.Project.x1 = min(New.Project.x1, Temp.x1);
  2304.     New.Project.x2 = max(New.Project.x2, Temp.x2);
  2305.     New.Project.y1 = min(New.Project.y1, Temp.y1);
  2306.     New.Project.y2 = max(New.Project.y2, Temp.y2);
  2307.  
  2308.     New.Entries++;
  2309.       }
  2310.     }
  2311.  
  2312.     /* If there are any visible entires, we'll use them. */
  2313.  
  2314.     if (New.Entries > 0)
  2315.     {
  2316.       /* If there's only one entry, we won't need a new node. */
  2317.  
  2318.       if (New.Entries == 1)
  2319.       {
  2320.     *Tree    = New.Entry[0];
  2321.     *Project = New.Project;
  2322.       }
  2323.       else
  2324.       {
  2325.     /* Allocate memory for new node in the vista tree (never freed!)  */
  2326.  
  2327.     *Tree = (PROJECT_TREE_NODE *)VB_malloc(sizeof(PROJECT_TREE_NODE));
  2328.  
  2329.     if (*Tree == NULL)
  2330.     {
  2331.       Fatal_MAError("vista tree node");
  2332.     }
  2333.  
  2334.     **Tree = New;
  2335.  
  2336.         /* Allocate memory for node/leaf entries. */
  2337.  
  2338.         (*Tree)->Entry = (PROJECT_TREE_NODE **)VB_malloc(New.Entries*sizeof(PROJECT_TREE_NODE *));
  2339.  
  2340.     if ((*Tree)->Entry == NULL)
  2341.     {
  2342.       Fatal_MAError("vista tree node");
  2343.     }
  2344.  
  2345.         memcpy((*Tree)->Entry, New.Entry, New.Entries*sizeof(PROJECT_TREE_NODE *));
  2346.  
  2347.     *Project = New.Project;
  2348.       }
  2349.     }
  2350.  
  2351.     /* Get rid of temporary node/leaf entries. */
  2352.  
  2353.     free(New.Entry);
  2354.   }
  2355.   else
  2356.   {
  2357.     /* Current object is a normal object, i.e. a leaf in the slab tree */
  2358.  
  2359.     /* Get object's projection */
  2360.  
  2361.     Project_Object(Object, Project);
  2362.  
  2363.     /* Is the object visible? */
  2364.  
  2365.     if ((Project->x1 <= Project->x2) && (Project->y1 <= Project->y2))
  2366.     {
  2367.       /* Allocate memory for new leaf in the vista tree (never freed!)  */
  2368.  
  2369.       *Tree = (PROJECT_TREE_NODE *)VB_malloc(sizeof(PROJECT_TREE_LEAF));
  2370.  
  2371.       if (*Tree == NULL)
  2372.       {
  2373.     Fatal_MAError("vista tree leaf");
  2374.       }
  2375.  
  2376.       /* Init new leaf */
  2377.  
  2378.       Leaf = (PROJECT_TREE_LEAF *)(*Tree);
  2379.  
  2380.       Leaf->Object = Object;
  2381.  
  2382.       Leaf->Project = *Project;
  2383.  
  2384.       /* Yes, this is a leaf */
  2385.  
  2386.       Leaf->is_leaf = TRUE;
  2387.     }
  2388.   }
  2389. }
  2390.  
  2391.  
  2392.  
  2393. /*****************************************************************************
  2394. *
  2395. * FUNCTION      : Build_Vista_Tree
  2396. *
  2397. * ARGUMENTS     : none
  2398. *
  2399. * MODIFIED ARGS : none
  2400. *
  2401. * RETURN VALUE  : none
  2402. *
  2403. * AUTHOR        : Dieter Bayer, May 1994
  2404. *
  2405. * DESCRIPTION
  2406. *
  2407. *   Build the vista tree, i.e. the 2d representation of the bounding slab
  2408. *   hierarchy in image space.
  2409. *
  2410. *   This only works for perspective and orthographic cameras.
  2411. *
  2412. * CHANGES
  2413. *
  2414. *   -
  2415. *
  2416. ******************************************************************************/
  2417.  
  2418. void Build_Vista_Tree()
  2419. {
  2420.   PROJECT Project;
  2421.  
  2422.   Root_Vista = NULL;
  2423.  
  2424.   if (Use_Slabs)
  2425.   {
  2426.     fprintf(stderr, "Building vista buffer");
  2427.  
  2428.     Begin_Point();
  2429.  
  2430.     Project_Bounding_Slab(&Project, &Root_Vista, Root_Object);
  2431.  
  2432.     End_Point();
  2433.   }
  2434. }
  2435.  
  2436.  
  2437.  
  2438. #endif
  2439.  
  2440.